#include <bits/stdc++.h>

using namespace std;

// 最长递增子序列的数量问题
// 给定一个未排序的整数数组nums，返回最长递增子序列的个数
// 测试链接 : https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

// O(N ^ 2) 的做法
class Solution 
{
public:
    int findNumberOfLIS(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> len(n, 1), count(n, 1);
        int retLen = 1, retCount = 1;
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0; j < i; ++j)
            {
                if(nums[j] < nums[i])
                {
                    if(len[j] + 1 == len[i])
                    {
                        count[i] += count[j];
                    }
                    else if(len[j] + 1 > len[i])
                    {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
            if(len[i] > retLen)
            {
                retLen = len[i];
                retCount = count[i];
            }
            else if(len[i] == retLen) retCount += count[i];
        }
        return retCount;
    }
};